#include"DynamicArray.h"
#include<iostream>
using ElementType= int;

DynamicArray::DynamicArray():m_capacity(10),m_size(0)
{
    a= new ElementType[m_capacity];
}

void DynamicArray::InsertTail(const ElementType &element)
{
    if(m_size>=m_capacity)
    {
        m_capacity *=2;
        ElementType *newP= new ElementType[m_capacity];
        for(int i=0; i< m_size; i++)
        {
            newP[i]=a[i];
        }
        delete []a;
        a= newP;
    }
    a[m_size++]= element;
}

void DynamicArray::show()
{
    for(int i=0; i<m_size; i++)
    {
        std::cout<<a[i]<<" ";
    }
    std::cout<<std::endl;
}

DynamicArray::~DynamicArray()
{
    delete []a;
}

DynamicArray::DynamicArray(const DynamicArray &s)
{
    std::cout<<"拷贝构造函数\n";
    m_capacity=s.m_capacity;
    m_size=s.m_size;
    for(int i=0; i<s.m_size; i++)
    {
        a[i]=s.a[i];
    }
}

void DynamicArray::operator=(const DynamicArray &s)
{
    std::cout<<"赋值运算符重载\n";
    m_capacity=s.m_capacity;
    m_size=s.m_size;
    for(int i=0; i<s.m_size; i++)
    {
        a[i]=s.a[i];
    }
}

ElementType DynamicArray::FindByElement(DynamicArray *array, ElementType element)
{
    for(int i=0; i<array->m_size; i++)
    {
        if(array->a[i]==element)
        return array->a[i];
    }
    return -1;
}

void DynamicArray::RemoveByIndex(DynamicArray *array, int index)
{
    if(index<0||index>=array->m_size)
    {
        printf("非法位置的删除\n");
        return;
    }

    for(int i= index; i< array->m_size; i++)
    {
        array->a[i]=array->a[i+1];
    }
}

void DynamicArray::RemoveByElement(DynamicArray *array, ElementType element)
{
    for(int i=0; i< array->m_size;i++)
    {
        if(array->a[i]==element) 
        {
            RemoveByIndex(array,i);
            array->m_size--;
            i--;
        }
    }
}

void DynamicArray::FastSort(ElementType *a, int start, int end)
{
    if(start>=end)
    return;

    int left= start;
    int right= end;
    int temp= a[left];
    while(left<right)
    {
        while (a[right]> temp && left<right)
        right--;
            
            if(left<right)
            {
            a[left]=a[right];
            left++;
            }
        
        while (a[left]<temp && left<right)
        left++;
            
            if(left<right)
            a[right--]= a[left];
    }
                a[left]=temp;
            FastSort(a,start,left-1);
            FastSort(a,right+1,end);
}

void DynamicArray::Sort(DynamicArray *a)
{
    FastSort(a->a,0,a->m_size-1);
}

int DynamicArray::BinarySearch(ElementType *a, int size, int element)
{
    int left=0;
    int right= size-1;
    while(left<=right)
    {
        int mid= left+(right-left)/2;
        // int mid= (left & right) + ((left ^ right)>>1);
    
    if(a[mid]>element)
    {
        right= mid-1;
    }
    else if(a[mid]<element)
    {
        left= mid+1;
    }
    else
    {
        return mid;
    }
    }
    return -1;
}

ElementType DynamicArray::Search(DynamicArray *a, ElementType number)
{
    return BinarySearch(a->a,a->m_size,number);
}
